﻿#include <iostream>
using namespace std;

#include <map>

//复制带随机指针的链表 C++
//https://leetcode.cn/problems/copy-list-with-random-pointer/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> m;
        Node* first = nullptr;
        Node* tail = nullptr;
        Node* cur = head;
        while (cur)
        {
            Node* node = new Node(cur->val); //原链表与新链表中的节点建立映射关系
            m[cur] = node;
            if (!first)
            {
                first = tail = node;
            }
            else
            {
                tail->next = node;
                tail = node;
            }
            cur = cur->next;
        }
        cur = head;
        while (cur)
        {
            if (!cur->random)
            {
                m[cur]->random = nullptr;
            }
            else
            {
                m[cur]->random = m[cur->random];
            }
            cur = cur->next;
        }
        return first;
    }
};